import java.util.*;

/**
 * 给定一个NX3的矩阵 matrix，对于每一个长度为3的小数组arr，都表示一个大楼的三个数据。arr[0]表示大楼的左边界，arr[1]表示大楼的右边界，arr[2]表示大楼的高度(一定大于0)。每座大楼的地基都在×轴上，大楼之间可能会有重叠，请返回整体的轮廓线数组。
 * 【举例】
 * matrix = {{2,5,6} ,{1,7,4} ,{4,6,7} ,{3,6,5} ,{10,13,2},{9,11,3} ,{12,14,4} ,{10,12,5}}
 * 返回:
 * [[1, 2, 4], [2, 4, 6], [4, 6, 7], [6, 7, 4], [9, 10, 3], [10, 12, 5], [12, 14, 4]]
 *
 * @author Liaorun
 */
public class BuildingOutline {

    public static void main(String[] args) {
        System.out.println(buildingOutline(new int[][]{{2, 5, 6}, {1, 7, 4}, {4, 6, 7}, {3, 6, 5}, {10, 13, 2}, {9, 11, 3}, {12, 14, 4}, {10, 12, 5}}));
    }

    public static class Node {
        /**
         * x轴上的值
         */
        public int x;

        /**
         * true 为加入，false为删除
         */
        public boolean isAdd;

        /**
         * 高度
         */
        public int h;

        public Node(int x, boolean isAdd, int h) {
            this.x = x;
            this.isAdd = isAdd;
            this.h = h;
        }
    }


    public static class NodeComparator implements Comparator<Node> {

        @Override
        public int compare(Node o1, Node o2) {
            if (o1.x != o2.x) {
                // x 有小到大排序
                return o1.x - o2.x;
            } else if (o1.isAdd != o2.isAdd) {
                // isAdd == true的在前面
                return o1.isAdd ? -1 : 1;
            } else {
                // 无所谓先后
                return 0;
            }
        }
    }

    public static List<List<Integer>> buildingOutline(int[][] matrix) {
        Node[] nodes = new Node[matrix.length * 2];
        // 每一个大楼的轮廓数组，产生两个描述高度变化的对象
        for (int i = 0; i < matrix.length; i++) {
            // 增加高度的对象
            nodes[i * 2] = new Node(matrix[i][0], true, matrix[i][2]);
            // 减少高度的对象
            nodes[i * 2 + 1] = new Node(matrix[i][1], false, matrix[i][2]);
        }

        // 把描述高度变化的对象数组，按照规定的排序策略排序
        Arrays.sort(nodes, new NodeComparator());

        // TreeMap就是java中的红黑树结构，直接当成有序表来使用
        // 高度出现次数的有序表
        TreeMap<Integer, Integer> mapHeightTimes = new TreeMap<>();
        // 每个位置对应的最高高度
        TreeMap<Integer, Integer> mapXHeight = new TreeMap<>();

        for (int i = 0; i < nodes.length; i++) {
            if (nodes[i].isAdd) {
                // 如果当前是加入的操作
                if (!mapHeightTimes.containsKey(nodes[i].h)) {
                    // 没有出现的高度，直接添加一条
                    mapHeightTimes.put(nodes[i].h, 1);
                } else {
                    // 出现的高度，出现的次数 + 1
                    mapHeightTimes.put(nodes[i].h, mapHeightTimes.get(nodes[i].h) + 1);
                }
            } else {
                if (mapHeightTimes.get(nodes[i].h) == 1) {
                    // 出现的次数记录 == 1，直接删除
                    mapHeightTimes.remove(nodes[i].h);
                } else {
                    // 出现的高度，出现的次数 - 1
                    mapHeightTimes.put(nodes[i].h, mapHeightTimes.get(nodes[i].h) - 1);
                }
            }

            if (mapHeightTimes.isEmpty()) {
                // 如果mapHeightTimes为 空，说明最大高度为0
                // 出现了楼房间的间隔
                mapXHeight.put(nodes[i].x, 0);
            } else {
                // 不为空，最后一个就是最大高度
                mapXHeight.put(nodes[i].x, mapHeightTimes.lastKey());
            }
        }

        // res 为结果数组，每一个List<Integer>代表一个轮廓线，
        // [开始位置，结束位置，高度]
        List<List<Integer>> res = new ArrayList<>();

        // 一个新轮廓线的开始位置
        int start = 0;
        // 之前的最大高度
        int preHeight = 0;

        // 根据mapXvalueHeight生成res数组
        for (Map.Entry<Integer, Integer> entry : mapXHeight.entrySet()) {
            // 当前位置
            Integer cur = entry.getKey();
            Integer curMaxHeight = entry.getValue();
            if (preHeight != curMaxHeight) {
                // 来到一个最高高度变化的地方
                if (preHeight != 0) {
                    // 一个轮廓结束的地方，需要记录一下
                    res.add(new ArrayList<>(Arrays.asList(start, cur, preHeight)));
                }

                // 当前位置的高度不为0，当前位置就是下一个轮廓开始的地方
                start = cur;
                // 当前位置的高度不为0，当前高度就是下一个轮廓的高度
                preHeight = curMaxHeight;
            }
        }

        return res;
    }
}
